As processing power and the number of supported applications increases in computer/digital/software based devices, there is an ever growing need for an increased number of timers that are operable to oversee a multitude of tasks within integrated circuit (IC) devices. However, as the number of timers increase, software solutions have become more expensive and less accurate. Hardware solutions to manage millions of timers running in parallel, which requires providing services for millions of counters, are problematic and often prohibitive in terms of cost, die space and power consumption.
Timers, generally, are counters that are fed with an initial duration value and a counting granularity, in order to create a ‘timer’ value. For example, a timer may be allocated a hundred time units, with a one second granularity, creating a one hundred second timer. Upon expiration of the timer, a timer node notifies the relevant timer creator that the timer has expired, and the relevant timer creator can proceed/process whatever it is programmed to do after expiration of the timer.
Different mechanisms are generally utilised for different timing duration distributions.
In the networking domain, millions of simultaneously running timers are generally utilised to manage networking flows and quality of service related aspects. Typically, in the network domain, timers would run with high resolution granularities (microseconds up to milliseconds) for relatively short durations.
In the domain of general purpose processors (GPP), for example tasks requiring switching/watchdog timers, a large amount of timers are also utilised to manage various applications. For typical GPP usage, there could be around tens of thousands of timers being run in parallel, which would generally be for lower resolutions (milliseconds up to seconds) and running for relatively long durations.
Generally, managing tens of thousands to millions of timers tends to require a large number of counters. These counters tend to take up a lot of silicon area and, therefore, cannot be physically located within the IC. Therefore, an algorithmic approach is generally utilised to manage the vast amount of timers, without having to physically represent the counters, which generally takes the form of timing rings/wheels.
Referring to FIG. 1, an example of a known timing wheel, comprising a simplified timing wheel, 100 is illustrated. Simplified timing wheel 100 comprises N number of slots 102, with six slots shown in this illustration, and a number of timers 104, 105, 106 associated with time slot 107, and timers 108, 109 associated with time slot 110. Each of the number of slots 102 represents a time unit, wherein a cursor 112 within the timing wheel 100 moves onto the next location every time unit, in the same manner as a second hand on a clock. In this case, the cursor 112 is currently located at timeslot 114, having previously been located at timeslot 107 at the previous time interval. When the cursor 112 moves onto timeslot 110, the timers 108 and 109 associated with timeslot 110 will expire at that instant, or when the cursor 112 reaches the timeslot 110 in subsequent cycles. The cursor 112 continues to increment onto subsequent time slots and wraps back to timeslot 107 after the cursor 112 increments past the final array entry.
The number of slots 102 in the timing wheel 100 has a limit that is defined by the array size of the timing wheel 100. For example, the maximum schedulable event that can be stored in the timing wheel could be 350 msec, but a 400 msec timing event needs to be stored. This leads to an overflow problem, wherein the 400 msec timing event cannot be stored.
As discussed above, different timing distributions require different timing mechanisms, resulting in potential problems if one mechanism is utilised for all timing distributions. In the networking domain, there is generally a need for millions of timers with short expiration times and a relatively small granularity, as they generally function in the ‘microsecond up to millisecond domain’. However, GPPs generally require a relatively larger granularity, as they tend to function up to the ‘second’ domain. Therefore, timing wheels for GPPs that have a large granularity will waste a lot of power during operation, for example when they are being monitored at a higher granularity level and may provide higher accuracy than needed. Further, utilising networking domain timing wheels for GPPs, would require a large number of timing wheels, due to the relatively smaller granularity, resulting in a large and expensive overhead, which affects the overall power/performance of devices.